package main

import . "local/datastructure/graph/am"

func dj(G AMGraph, vo int) {
	//初始化
	D := make([]int, G.NumVers)
	P := make([]int, G.NumVers)
	visited := make([]bool, G.NumVers)
	for i := 0; i < G.NumVers; i++ {
		D[i] = G.Arcs[vo][i]
		P[i] = -1
	}
	visited[0] = true

	//循环查找下一个顶点
	for i := 1; i < G.NumVers; i++ {
		//scan: 寻找未访问节点中最小距离顶点
		min := INF
		var k int
		for j := 0; j < G.NumVers; j++ {
			if !visited[j] && min < D[j] {
				k = j
				min = D[j]
			}
		}

		visited[k] = true
		for j2 := 0; j2 < G.NumVers; j2++ {
			if !visited[j2] && (min+G.Arcs[k][j2]) < D[j2] {
				D[j2] = min + G.Arcs[k][j2]
				P[j2] = k
			}
		}
	}
}
